{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Title: #Largest Element in an Array after Merge Operations"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Difficulty: #Medium"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Category Title: #Algorithms"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tag Slug: #greedy #array #prefix-sum"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Name Translated: #贪心 #数组 #前缀和"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution Name: maxArrayValue"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Title: #合并后数组中的最大元素"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Content:\n",
    "<p>给你一个下标从 <strong>0</strong> 开始、由正整数组成的数组 <code>nums</code> 。</p>\n",
    "\n",
    "<p>你可以在数组上执行下述操作 <strong>任意</strong> 次：</p>\n",
    "\n",
    "<ul>\n",
    "\t<li>选中一个同时满足&nbsp;<code>0 &lt;= i &lt; nums.length - 1</code> 和 <code>nums[i] &lt;= nums[i + 1]</code> 的整数 <code>i</code> 。将元素 <code>nums[i + 1]</code> 替换为 <code>nums[i] + nums[i + 1]</code> ，并从数组中删除元素 <code>nums[i]</code> 。</li>\n",
    "</ul>\n",
    "\n",
    "<p>返回你可以从最终数组中获得的 <strong>最大</strong> 元素的值。</p>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>示例 1：</strong></p>\n",
    "\n",
    "<pre><strong>输入：</strong>nums = [2,3,7,9,3]\n",
    "<strong>输出：</strong>21\n",
    "<strong>解释：</strong>我们可以在数组上执行下述操作：\n",
    "- 选中 i = 0 ，得到数组 nums = [<strong><em>5</em></strong>,7,9,3] 。\n",
    "- 选中 i = 1 ，得到数组 nums = [5,<em><strong>16</strong></em>,3] 。\n",
    "- 选中 i = 0 ，得到数组 nums = [<em><strong>21</strong></em>,3] 。\n",
    "最终数组中的最大元素是 21 。可以证明我们无法获得更大的元素。\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 2：</strong></p>\n",
    "\n",
    "<pre><strong>输入：</strong>nums = [5,3,3]\n",
    "<strong>输出：</strong>11\n",
    "<strong>解释：</strong>我们可以在数组上执行下述操作：\n",
    "- 选中 i = 1 ，得到数组 nums = [5,<em><strong>6</strong></em>] 。\n",
    "- 选中 i = 0 ，得到数组 nums = [<em><strong>11</strong></em>] 。\n",
    "最终数组中只有一个元素，即 11 。\n",
    "</pre>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>提示：</strong></p>\n",
    "\n",
    "<ul>\n",
    "\t<li><code>1 &lt;= nums.length &lt;= 10<sup>5</sup></code></li>\n",
    "\t<li><code>1 &lt;= nums[i] &lt;= 10<sup>6</sup></code></li>\n",
    "</ul>\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Description: [largest-element-in-an-array-after-merge-operations](https://leetcode.cn/problems/largest-element-in-an-array-after-merge-operations/description/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solutions: [largest-element-in-an-array-after-merge-operations](https://leetcode.cn/problems/largest-element-in-an-array-after-merge-operations/solutions/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_cases = ['[2,3,7,9,3]', '[5,3,3]']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxArrayValue(self, A: List[int]) -> int:\n",
    "        res = 0\n",
    "        while A:\n",
    "            cur = A.pop()\n",
    "            while A and A[-1] <= cur: cur += A.pop()\n",
    "            res = max(res, cur)\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxArrayValue(self, nums: List[int]) -> int:\n",
    "        i = len(nums) - 2\n",
    "        while (i >= 0): \n",
    "            if nums[i] <= nums[i + 1]:\n",
    "                nums[i + 1] = nums[i] + nums[i + 1]\n",
    "                del nums[i]\n",
    "            i = i - 1\n",
    "        return max(nums)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxArrayValue(self, nums: List[int]) -> int:\n",
    "        for i in range(len(nums)-1, 0, -1):\n",
    "            if nums[i] >= nums[i-1]:\n",
    "                nums[i] += nums[i-1]\n",
    "                nums.pop(i-1)\n",
    "        return max(nums)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxArrayValue(self, nums: List[int]) -> int:\n",
    "\n",
    "        def isNotReverseList(nums):\n",
    "            value = nums[0]\n",
    "            for i in range(1,len(nums)):\n",
    "                if nums[i] < value:\n",
    "                    value = nums[i]\n",
    "                    continue\n",
    "                else:return True\n",
    "            return False\n",
    "\n",
    "        def findindex(nums):\n",
    "            for i in range(len(nums)-2,-1,-1):\n",
    "                if nums[i] <= nums[i+1]:\n",
    "                    return i\n",
    "\n",
    "\n",
    "        # print(isNotReverseList(nums))                \n",
    "        while isNotReverseList(nums):\n",
    "            index = findindex(nums)\n",
    "            value = nums[index] + nums[index + 1]\n",
    "            nums.pop(index)\n",
    "            nums.pop(index)\n",
    "            nums.insert(index,value)\n",
    "\n",
    "        return nums[0]\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxArrayValue(self, nums: List[int]) -> int:\n",
    "        i=len(nums)-1\n",
    "        while i>0:\n",
    "            if nums[i]>=nums[i-1]:\n",
    "                nums[i-1]+=nums[i]\n",
    "                nums.pop(i)\n",
    "            i-=1\n",
    "        return max(nums)\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxArrayValue(self, nums: List[int]) -> int:\n",
    "        n=len(nums)-1\n",
    "        while n>=1:\n",
    "            if nums[n]>=nums[n-1]:\n",
    "                nums[n]=nums[n]+nums[n-1]\n",
    "                del nums[n-1]\n",
    "            n=n-1\n",
    "        return max(nums)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxArrayValue(self, nums: List[int]) -> int:\n",
    "        n = len(nums)\n",
    "        for i in range(n-1,0,-1):\n",
    "            if nums[i] >= nums[i-1]:\n",
    "                nums[i-1],nums[i] = nums[i]+nums[i-1],0\n",
    "        return max(nums)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from collections import *\n",
    "from heapq import *\n",
    "from sys import *\n",
    "from math import *\n",
    "from itertools import *\n",
    "from functools import *\n",
    "from string import *\n",
    "from bisect import *\n",
    "from graphlib import *\n",
    "from sortedcontainers import *\n",
    "from copy import *\n",
    "\n",
    "class Solution:\n",
    "    def maxArrayValue(self, nums: List[int]) -> int:\n",
    "        ans = nums[-1]\n",
    "        while len(nums) > 1:\n",
    "            if nums[-1] >= nums[-2]: \n",
    "                nums[-2] += nums[-1]\n",
    "            nums.pop()\n",
    "            ans = max(ans, nums[-1])\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxArrayValue(self, nums: List[int]) -> int:\n",
    "        n = len(nums)\n",
    "        for i in range(n-1,0,-1):\n",
    "            if nums[i] >= nums[i-1]:\n",
    "                nums[i-1],nums[i] = nums[i]+nums[i-1],0\n",
    "        return max(nums)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxArrayValue(self, nums: List[int]) -> int:\n",
    "        n = len(nums)\n",
    "        i = n - 1\n",
    "        flag = False\n",
    "        while i > 0:\n",
    "            if nums[i] >= nums[i - 1] and nums[i - 1] > 0:\n",
    "                flag = True\n",
    "                nums[i - 1] += nums[i]\n",
    "                nums[i] = 0\n",
    "            i -= 1\n",
    "        if not flag:\n",
    "            return max(nums)\n",
    "        else:\n",
    "            return self.maxArrayValue(nums)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxArrayValue(self, nums: List[int]) -> int:\n",
    "        n = len(nums)\n",
    "        i = n-1\n",
    "        ans = -inf\n",
    "        while i > 0:\n",
    "            \n",
    "            if nums[i] >= nums[i-1]:\n",
    "                # nums[i] = nums[i] + nums[i-1]\n",
    "                # nums[i-1] = 0\n",
    "                nums[i-1] = nums[i] + nums[i-1]\n",
    "                nums[i] = 0\n",
    "                ans = max(ans, nums[i-1])\n",
    "                # i = 0\n",
    "                # nums.remove(0)\n",
    "                # continue\n",
    "            i -= 1\n",
    "        return max(ans, max(nums))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxArrayValue(self, nums: List[int]) -> int:\n",
    "        # res = 0\n",
    "        # n = len(nums)\n",
    "        # @cache\n",
    "        # def dfs(i):\n",
    "        #     nonlocal res\n",
    "        #     if i == n-1:\n",
    "        #         # j = 0\n",
    "        #         # while j < n-1:\n",
    "        #         #     if nums[j] != 0 and nums[j] <= nums[j+1]:\n",
    "        #         #         dfs(0)\n",
    "        #         #         j = 0\n",
    "        #         #     else:\n",
    "        #         #         j += 1\n",
    "        #         res = max(nums)\n",
    "        #         return\n",
    "        #     if nums[i] != 0 and nums[i] <= nums[i+1]:\n",
    "        #         dfs(i+1)\n",
    "        #         nums[i+1] += nums[i]\n",
    "        #         c = nums[i]\n",
    "        #         nums[i] = 0\n",
    "        #         dfs(i+1)\n",
    "        #         # nums[i+1] -= c\n",
    "        #         # nums[i] = c\n",
    "        #     else:\n",
    "        #         dfs(i+1)\n",
    "        # dfs(0)\n",
    "        \n",
    "        \n",
    "        # res = 0\n",
    "        n = len(nums)\n",
    "        i = n-1\n",
    "        c = 0\n",
    "        while i > 0:\n",
    "            if nums[i] == 0:\n",
    "                i -= 1\n",
    "                continue\n",
    "            j = i-1-c\n",
    "            while j >= 0 and nums[j] == 0:\n",
    "                    j -= 1\n",
    "            if j < 0:\n",
    "                break\n",
    "            if nums[j] <= nums[i]:\n",
    "                nums[i] += nums[j]\n",
    "                nums[j] = 0\n",
    "                c += 1\n",
    "            else:\n",
    "                i -= 1+c\n",
    "                c = 0\n",
    "        return max(nums)\n",
    "        \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxArrayValue(self, nums: List[int]) -> int:\n",
    "        #从右边开始计算就能保证最大\n",
    "        n=len(nums)\n",
    "        i=n-1\n",
    "        while i>0 and n>1:\n",
    "            for j in range(i-1,-1,-1):\n",
    "                if nums[j]<=nums[i]:\n",
    "                    nums[i]=nums[j]+nums[i]\n",
    "                    nums[j]=0\n",
    "                    n-=1\n",
    "                else:\n",
    "                    i=j\n",
    "        return max(nums)\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxArrayValue(self, nums: List[int]) -> int:\n",
    "        n = len(nums)\n",
    "        i = n-1\n",
    "        ans = -inf\n",
    "        while i > 0:\n",
    "            \n",
    "            if nums[i] >= nums[i-1]:\n",
    "                # nums[i] = nums[i] + nums[i-1]\n",
    "                # nums[i-1] = 0\n",
    "                nums[i-1] = nums[i] + nums[i-1]\n",
    "                nums[i] = 0\n",
    "                ans = max(ans, nums[i-1])\n",
    "                # i = 0\n",
    "                # nums.remove(0)\n",
    "                # continue\n",
    "            i -= 1\n",
    "        return max(ans, max(nums))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxArrayValue(self, nums: List[int]) -> int:\n",
    "        nums.reverse()\n",
    "        Max = nums[0]\n",
    "        for num in nums[1:]:\n",
    "            if Max >= num:\n",
    "                Max += num\n",
    "            else:\n",
    "                Max = num\n",
    "        return Max\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxArrayValue(self, nums: List[int]) -> int:\n",
    "        ans = 0\n",
    "        for num in nums[::-1]:\n",
    "            if ans >= num:\n",
    "                ans += num \n",
    "            else:\n",
    "                ans = num \n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxArrayValue(self, nums: List[int]) -> int:\n",
    "        res, tmp = 0, 0\n",
    "        for i in nums[::-1]:\n",
    "            if i>tmp:\n",
    "                res = max(res,i)\n",
    "                tmp = i\n",
    "            else:\n",
    "                tmp+=i\n",
    "                res = max(res,tmp)\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxArrayValue(self, nums: List[int]) -> int:\n",
    "        nums = nums[::-1]\n",
    "        res = 0\n",
    "        for i in nums:\n",
    "            if res < i : res = i\n",
    "            else : res += i\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxArrayValue(self, nums: List[int]) -> int:\n",
    "        res = 0\n",
    "        for i in nums[::-1]:\n",
    "            if res >= i:\n",
    "                res += i\n",
    "            else:\n",
    "                res = i\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxArrayValue(self, nums: List[int]) -> int:\n",
    "        now = nums[-1]\n",
    "        n = len(nums)\n",
    "        for index in range(n - 2, -1, -1):\n",
    "            if now >= nums[index]:\n",
    "                now += nums[index]\n",
    "            else:\n",
    "                now = nums[index]\n",
    "        \n",
    "        return now"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxArrayValue(self, nums: List[int]) -> int:\n",
    "        ans = 0\n",
    "        i = len(nums)-1\n",
    "        while i >= 0:\n",
    "            s = nums[i]\n",
    "            i -= 1\n",
    "            while i >= 0 and nums[i] <= s:\n",
    "                s += nums[i]\n",
    "                i -= 1\n",
    "            ans = max(ans,s)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxArrayValue(self, nums: List[int]) -> int:\n",
    "        ans = ans1 = 0\n",
    "        for i in range(len(nums) - 1, -1, -1):\n",
    "            if nums[i] <= ans1: ans1 += nums[i]\n",
    "            else: ans, ans1 = max(ans, ans1), nums[i]\n",
    "        return max(ans, ans1)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxArrayValue(self, nums: List[int]) -> int:\n",
    "        ans = ans1 = 0\n",
    "        for i in range(len(nums) - 1, -1, -1):\n",
    "            if nums[i] <= ans1: ans1 += nums[i]\n",
    "            else: ans, ans1 = max(ans, ans1), nums[i]\n",
    "        return max(ans, ans1)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxArrayValue(self, nums: List[int]) -> int:\n",
    "        n = len(nums)\n",
    "        ans = 0\n",
    "        for i in range(n-1,-1,-1):\n",
    "            if ans < nums[i]:\n",
    "                ans = nums[i]\n",
    "            else:\n",
    "                ans += nums[i]\n",
    "        return ans\n",
    "        # n = len(nums)\n",
    "        # for i in range(n-2,-1,-1):\n",
    "        #     if nums[i] <= nums[i + 1]:\n",
    "        #         nums[i] += nums[i+1]\n",
    "        # return max(nums)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxArrayValue(self, nums: List[int]) -> int:\n",
    "        n=len(nums)\n",
    "        for i in range(n-1,0,-1):\n",
    "            if nums[i]>=nums[i-1]:\n",
    "                nums[i-1]+=nums[i]\n",
    "        return max(nums)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxArrayValue(self, nums: List[int]) -> int:\n",
    "        n = len(nums)\n",
    "        ans = 0\n",
    "        i = n - 1\n",
    "        while i >= 0:\n",
    "            j = i\n",
    "            crt_sum = nums[j]\n",
    "            while j > 0 and crt_sum >= nums[j - 1]:\n",
    "                crt_sum += nums[j - 1]\n",
    "                j -= 1\n",
    "            ans = max(ans, crt_sum)\n",
    "            i = j - 1\n",
    "        return ans\n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxArrayValue(self, nums: List[int]) -> int:\n",
    "        n = len(nums)\n",
    "        flag = True\n",
    "        res = 0\n",
    "        temp = nums[-1]\n",
    "        for i in range(n-2,-1,-1):\n",
    "            if temp >= nums[i]:\n",
    "                temp+=nums[i]\n",
    "            else:\n",
    "                res = max(res,temp)\n",
    "                temp = nums[i]\n",
    "        return max(res,temp)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxArrayValue(self, nums: List[int]) -> int:\n",
    "        ans1=0\n",
    "        for i in range(len(nums)-1,-1,-1):\n",
    "            if nums[i]<=ans1:\n",
    "                ans1+=nums[i]\n",
    "            else:ans1=nums[i]\n",
    "        return ans1\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxArrayValue(self, nums: List[int]) -> int:\n",
    "        ans1=0\n",
    "        for i in range(len(nums)-1,-1,-1):\n",
    "            if nums[i]<=ans1:\n",
    "                ans1+=nums[i]\n",
    "            else:ans1=nums[i]\n",
    "        return ans1\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxArrayValue(self, nums: List[int]) -> int:\n",
    "        if len(nums) == 1:return nums[0]\n",
    "        i = len(nums) - 1; ans = 0; tem = nums[-1]\n",
    "        while i > 0:\n",
    "            tem = tem + nums[i-1] if tem >= nums[i-1] else nums[i-1]\n",
    "            i -= 1\n",
    "            ans = max(ans, tem)\n",
    "        return ans\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxArrayValue(self, nums: List[int]) -> int:\n",
    "        ans = nums[-1]\n",
    "        tmp = nums[-1]\n",
    "        for i in range(len(nums)-2, -1, -1) :\n",
    "            if tmp >= nums[i] :\n",
    "                tmp += nums[i]\n",
    "            else :\n",
    "                tmp = nums[i]\n",
    "            ans = max(ans, tmp)\n",
    "                \n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxArrayValue(self, nums: List[int]) -> int:\n",
    "        res = nums[0]\n",
    "        for i in reversed(range(1, len(nums))):\n",
    "            if nums[i] >= nums[i - 1]:\n",
    "                nums[i - 1] += nums[i]\n",
    "                res = max(res, nums[i - 1])\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxArrayValue(self, nums: List[int]) -> int:\n",
    "        tmp=nums[-1]\n",
    "        res=tmp\n",
    "        for i in range(1,len(nums)):\n",
    "            if tmp>=nums[len(nums)-i-1]:\n",
    "                tmp+=nums[len(nums)-i-1]\n",
    "            else:\n",
    "                tmp=nums[len(nums)-i-1]\n",
    "            res=max(res,tmp)\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxArrayValue(self, nums: List[int]) -> int:\n",
    "        n = len(nums)\n",
    "        ans = 0\n",
    "        for i in range(n-1, 0, -1):\n",
    "            ans = max(ans, nums[i])\n",
    "            if nums[i] >=  nums[i-1]:\n",
    "                nums[i-1] += nums[i]\n",
    "        return max(nums[0], ans)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxArrayValue(self, nums: List[int]) -> int:\n",
    "        n = len(nums)\n",
    "        res = nums[-1]\n",
    "        for i in range(n-2, -1, -1):\n",
    "            if nums[i]<=nums[i+1]:\n",
    "                nums[i] = nums[i] + nums[i+1]\n",
    "            res = max(res, nums[i])\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxArrayValue(self, nums: List[int]) -> int:\n",
    "        n = len(nums)\n",
    "        for i in range(n-1,0,-1):\n",
    "            if nums[i] >= nums[i-1]:\n",
    "                nums[i-1] += nums[i]\n",
    "        return nums[0]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxArrayValue(self, nums: List[int]) -> int:\n",
    "        n=len(nums)\n",
    "        if n==1:\n",
    "            return nums[0]\n",
    "        i=n-1\n",
    "        while i>0:\n",
    "            while i>0 and nums[i-1]<=nums[i]:\n",
    "                nums[i-1]+=nums[i]\n",
    "                i-=1\n",
    "            if i==0:\n",
    "                return nums[i]\n",
    "            else:\n",
    "                i-=1\n",
    "                if i==0:\n",
    "                    return nums[i]       "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxArrayValue(self, nums: List[int]) -> int:\n",
    "        n = len(nums)\n",
    "        for i in range(n-2, -1, -1):\n",
    "            if nums[i]<=nums[i+1]:\n",
    "                nums[i] += nums[i+1]\n",
    "\n",
    "        return nums[0]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxArrayValue(self, nums: List[int]) -> int:\n",
    "        n=len(nums)\n",
    "        if n==1:\n",
    "            return nums[0]\n",
    "        i=n-1\n",
    "        while i>0:\n",
    "            while i>0 and nums[i-1]<=nums[i]:\n",
    "                nums[i-1]+=nums[i]\n",
    "                i-=1\n",
    "            if i==0:\n",
    "                return nums[i]\n",
    "            else:\n",
    "                i-=1\n",
    "                if i==0:\n",
    "                    return nums[i]\n",
    "        # def short(nums):\n",
    "        #     res=[]\n",
    "        #     n=len(nums)\n",
    "        #     i=0\n",
    "        #     while i<n:\n",
    "        #         t=0\n",
    "        #         while i<n-1 and nums[i]<=nums[i+1]:\n",
    "        #             t+=nums[i]\n",
    "        #             i+=1\n",
    "        #         if i==n-1:\n",
    "        #             res.append(t+nums[i])\n",
    "        #             i+=2\n",
    "        #         else:\n",
    "        #             res.append(t+nums[i])\n",
    "        #             i+=1\n",
    "        #     print(res)\n",
    "        #     return res\n",
    "\n",
    "        # t=short(nums)\n",
    "        # while t!=nums:\n",
    "        #     nums=t\n",
    "        #     t=short(nums)\n",
    "        # return max(nums)            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxArrayValue(self, nums: List[int]) -> int:\n",
    "        n = len(nums)\n",
    "        ans = 0\n",
    "        for i in range(n - 2, -1, -1):\n",
    "            if nums[i] <= nums[i + 1]:\n",
    "                nums[i] += nums[i + 1]\n",
    "        return max(nums)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxArrayValue(self, nums: List[int]) -> int:\n",
    "        nums.reverse()\n",
    "        print(nums)\n",
    "        for i in range(len(nums)-1):\n",
    "            if nums[i]>=nums[i+1]:\n",
    "                nums[i+1]+=nums[i]\n",
    "        return nums[-1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxArrayValue(self, nums: List[int]) -> int:\n",
    "        n = len(nums)\n",
    "        ans = nums[-1]\n",
    "        nums.insert(0,0)\n",
    "        pre = [0] * (n+1)\n",
    "        pre[-1] = nums[-1]\n",
    "        for i in range(n,0,-1):\n",
    "            if pre[i]>=nums[i-1]:\n",
    "                pre[i-1]=pre[i]+nums[i-1]\n",
    "            else:\n",
    "                pre[i-1]=nums[i-1]\n",
    "            ans = max(ans,pre[i-1])\n",
    "            print(ans)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxArrayValue(self, nums: List[int]) -> int:\n",
    "        m = len(nums)\n",
    "        dp = [0] * (m)\n",
    "        dp[-1] = nums[-1]\n",
    "        for i in range(m-2, -1, -1): \n",
    "            if nums[i] <= dp[i+1]:\n",
    "                dp[i] = nums[i] + dp[i+1]\n",
    "            else:\n",
    "                dp[i] = max(nums[i], dp[i+1])\n",
    "        return dp[0]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxArrayValue(self, nums: List[int]) -> int:\n",
    "        n = len(nums)\n",
    "        q = deque()\n",
    "        ans = 0\n",
    "        for num in nums[::-1]:\n",
    "            while q and q[-1] < num:\n",
    "                t = q.pop()\n",
    "                ans = max(ans, t)\n",
    "                if not q:\n",
    "                    break\n",
    "                q[-1] += t\n",
    "            q.append(num)\n",
    "            while len(q) > 1 and q[-1] <= q[-2]:\n",
    "                t = q.pop()\n",
    "                q[-1] += t\n",
    "            # print(q)\n",
    "        return q[-1]\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxArrayValue(self, nums: List[int]) -> int:\n",
    "\n",
    "        n = len(nums)\n",
    "        for i in range(1, n):\n",
    "            if nums[n-i-1] <= nums[n-i]:\n",
    "                nums[n-i-1] += nums[n-i]\n",
    "        print(nums)\n",
    "        return max(nums)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxArrayValue(self, nums: List[int]) -> int:\n",
    "        result = nums[-1]\n",
    "        for i in range(len(nums)-1, 0,-1):\n",
    "            if nums[i] >= nums[i-1]:\n",
    "                nums[i-1] += nums[i]\n",
    "            result = max(nums[i-1],result)\n",
    "        print(nums)\n",
    "        return result"
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 2
}
